package com.mamingchao.basic.swardToOffer.two;

/**
 * 给定一个非负整数n,代表二叉树的节点个数。返回能形成多多少种不同的二叉树结构
 * 方案：这个就递归==》 动态规划即可
 */
public class CalNumOfBinaryTree {

    public static void main(String[] args) {
        System.out.println("递归方式的计算结果：" + getBinaryTreeCount(5));
        System.out.println("动态规划方式的计算结果：" + dynamicPlan(5));
    }

    /**
     * 普通递归的实现方式
     * @param treeNodeNum 二叉树的节点
     * @return 可以生成二叉树 的数量
     */
    private static int getBinaryTreeCount(int treeNodeNum) {
        // base case
        if (treeNodeNum == 2) {
            return 2;
        } else if (treeNodeNum < 2){
            return 1;
        }
        
        int result=0;
        // i是左子树的节点数量
        for (int i = 0; i < treeNodeNum; i++) {
            result  += getBinaryTreeCount(i) * getBinaryTreeCount(treeNodeNum-1-i);
        }
        return  result;
    }

    /**
     * 动态规划的计算方式
     * @param treeNodeNum 二叉树的节点
     * @return 可以生成二叉树 的数量
     */
    private static int dynamicPlan(int treeNodeNum) {

        int[] dp = new int[treeNodeNum+1];

        // base case
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        // i是左子树的节点数量
        for (int i = 3; i <= treeNodeNum; i++) {

            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i-j-1];
            }
        }

        return  dp[treeNodeNum];
    }
}
